The present invention relates to Decision Feedback Sequence Estimation.
In a cellular Time Division Multiple Access (TDMA) system, Inter-Symbol Interference (ISI) introduced by bandwidth limited modulation and a multipath radio channel is removed by a channel equalizer. The radio channel in such a system (including the transmitter and receiver filter) can usually be modeled by:                                           b            ⁡                          (              k              )                                =                                                    ∑                                  j                  =                  0                                L                            ⁢                                                a                  ⁡                                      (                                          k                      -                      j                                        )                                                  ·                                  h                  ⁡                                      (                    j                    )                                                                        +                          n              ⁡                              (                k                )                                                    ,                            (        1        )            
where b(k) are the received symbol spaced signal samples and h(j) are the taps of a time discrete baseband model of the multipath channel, that is, a model of the ISI introduced by the channel and filters. The variable a(kxe2x88x92j) represents the transmitted symbols and n(k) is additive white Gaussian noise. The channel influence on h will change with time, but can be modeled to be constant under a short enough time interval.
Between the time that symbols, a(k) are generated at a transmitter and the time they are recreated (estimated) at a receiver, they may be altered by various mechanisms. For example, as illustrated in FIG. 1a, at the transmitter the symbols a(k) may first be modified by a transmitter filter 101. The transmitted signal may then undergo further modification by means of a multipath channel 103, before it is received by a receiver filter 105. The received signal, b(t) must then be converted into digital form by a sampling circuit 107, which generates distorted samples b(k). The distorted samples b(k) are then supplied to an equalizer 109, which finally generates the estimated symbols xc3xa2(k).
At the receiver, the transmitter filter 101, multipath channel 103, receiver filter 105 and sampling circuit 107 are usually modeled as a time discrete finite impulse response (FIR) filter 111, as illustrated in FIG. 1b. The FIR filter 111 is estimated to have an estimated response, ĥ, that operates on the transmitted symbols, a(k), in accordance with equation (1). The estimated response, ĥ, is used by the succeeding equalizer 109 in a process that generates estimated symbols, xc3xa2(k), based on the received distorted samples, b(k). FIGS. 1a and 1b illustrate a linear modulation scheme, but continuous phase modulations, such as that used in GSM systems, can as well often be interpreted this way by the receiver.
The equalizer 109 may operate in accordance with any of a number of known symbol estimation techniques. If the goal is to minimize symbol sequence error, a Maximum Likelihood Sequence Estimator (MLSE) provides optimum performance. In the MLSE, the symbol sequence which minimizes the Euclidean distance between the symbol sequence filtered through the channel, and the received sample sequence is found. Assuming white Gaussian noise, this symbol sequence is the most probable one. If the Viterbi algorithm is used to implement the MLSE, the sequence is found in a step-by-step iterative technique that involves calculating metrics. Some of the components in these metrics only depend on the symbol alphabet and the channel estimate. Since these components are used many times in the Viterbi algorithm and are independent of the received samples, they can be pre-calculated once per channel estimate, and stored in tables, thus saving complexity. This is described, for example, in U.S. Pat. No. 5,091,918, which issued to Wales on Feb. 25, 1992. The same approach is possible for a Maximum A Posteriori (MAP) equalizer since the same metrics are needed. It is noted that a non-simplified MAP symbol-by-symbol equalizer can offer lower symbol error rate, and can also provide somewhat better soft values and hence improve the decoded performance.
Examined more closely, conventional MLSE techniques operate by hypothesizing candidate sequences, and for each candidate sequence calculating metrics in the form                               dM          =                      |                                          y                ⁡                                  (                  k                  )                                            -                                                ∑                                      j                    =                    0                                                        L                    MLSE                                                  ⁢                                                      a                    ⁡                                          (                                              k                        -                        j                                            )                                                        ·                                                            h                      ^                                        ⁡                                          (                      j                      )                                                                                            ⁢                          |              2                                      ,                            (        2        )            
where y(k) are the received samples, a(k) are the symbols of a candidate sequence, LMLSE+1 is the number of MLSE taps in the equalizer window, and ĥ(j) is the channel estimate. Since a(kxe2x88x92j) and ĥ(j) are independent of the received signal, it is possible to reduce the number of computations for a given channel estimate by calculating the hypothesized received sample values (i.e., the sum in equation 2, henceforth referred to as a hypothesis) for all possible hypothesized symbols, and storing these precalculated sums in a memory. These precalculated values, which are retrieved as needed to determine a branch metric (dM) for a particular received sample y(k), are used many times in the equalization process. Since all MLMLSE+1 branch metrics (dM) are needed per sample, computations are always saved using precalculation.
An example is shown below in Table 1. In this example, let the channel be h=[2 j], and let LMLSE+1=2. Assume that the symbol alphabet is a(k)={xe2x88x921,1,xe2x88x92j,j} (e.g., Quadrature Phase Shift Keying, or QPSK). The possible hypotheses, A(k), then become those shown in Table 1:
It will be observed that A(k) is independent of k, and can be re-used for all samples. It is apparent that complexity can be saved by setting up this table once per channel estimate.
Despite the complexity savings from using precalculated hypotheses in a look-up table, the MLSE algorithm can become computationally intense as the size of the equalization window (i.e., the number of taps in the channel model) grows, and also as higher order modulation is used, because the complexity is proportional to (#Symbols in modulation alphabet)Window Size. The need for such growth is driven by the evolution into higher symbol transmission rates, which are being proposed in order to offer high bit rates in future communications systems. The Enhanced Data rates for Global Evolution (EDGE) cellular telecommunications standard is one such system in which higher level modulation (HLM) is proposed. A known alternative equalization technique that requires fewer computations, and which therefore may be suitable for use in such new communications standards, is Decision Feedback Estimation (DFE). Unlike MLSE, which uses a sequence detection strategy, DFE detects symbols on a symbol-by-symbol basis. This is accomplished by first estimating a value that represents the signal energy presently experienced from previously decoded symbols. This energy value is then subtracted from a current received sample, in order to cancel out ISI. Because the energy value is determined from an estimate of the channel response and from previously decoded symbols, the form of energy value computation resembles that of the MLSE""s hypothesis computation. However, because calculating the energy value for DFE need only be performed for previously decoded symbols (i.e., the previously generated final output symbols from the DFE), as opposed to a complete set of hypothesized symbol sequences in the case of MLSE, computational complexity of the DFE approach is substantially less than that for MLSE.
As one would expect, the relatively lower computational complexity of DFE is accompanied by a relatively higher symbol error rate, when compared to the MLSE approach. It is nonetheless preferable to MLSE in some cases because the total storage (complexity) of the MLSE algorithm is proportional to the number of states of the trellis which grows exponentially with the channel memory length. When the channel memory becomes large (it can be infinite), the MLSE algorithm becomes impractical.
A compromise solution may be found in the form of a Decision Feedback Sequence Estimator (DFSE). DFSEs are known, and are described in, for example, A. Duel-Hallen et al., xe2x80x9cDelayed Decision-Feedback Sequence Estimationxe2x80x9d, IEEE Transactions on Communications, pp. 428-436, vol. 37, No. 5, May 1989. The complexity of a DFSE is controlled by a parameter xcexc that can be varied from zero to the size of the memory of the channel. The algorithm is based on a trellis with the number of states being exponential in xcexc. When xcexc=0, DFSE reduces to the DFE. When the memory of the channel is finite, DFSE with maximal complexity is equivalent to the Viterbi algorithm. For the intermediate values of xcexc, DFSE can be described as a reduced-state Viterbi algorithm with feedback incorporated into the structure of path metric computations.
Thus, for a given window size, DFSE can be significantly less complex than the MLSE approach. The basic principle is to divide the channel taps into one MLSE part 201 of relatively high complexity, and one DFE part 203 having relatively lower complexity, as shown in FIG. 2. That is, for a DFSE the channel estimate is divided into two parts: {ĥ(0), . . . , ĥ(LMLSE)}, which are the channel estimates for the MLSE taps 201, and {ĥ(LMLSE+1), . . . , ĥ(LMLSE+LDFE)}, which are the channel estimates for the DFE taps 203, as shown in FIG. 2. The branch metrics then become                     dM        =                  |                                    y              ⁡                              (                k                )                                      -                                          ∑                                  j                  =                  0                                                  L                  MLSE                                            ⁢                                                a                  ⁡                                      (                                          k                      -                      j                                        )                                                  ·                                                      h                    ^                                    ⁡                                      (                    j                    )                                                                        -                                          ∑                                  j                  =                                                            L                      MLSE                                        +                    1                                                                                        L                    MLSE                                    +                                      L                    DFE                                                              ⁢                                                                    a                    _                                    ⁡                                      (                                          k                      -                      j                                        )                                                  ·                                                      h                    ^                                    ⁡                                      (                    j                    )                                                                                ⁢                      |            2                                              (        3        )            
where {overscore (a)}(k) are the old tentative symbol decisions corresponding to the path into a state and LDFE is the number of feedback taps. It will be apparent that the tentative symbol decisions used in calculating a DFSE metric may differ from one decoding trellis path to another. Observe that the size of the equalization window is LMLSE+LDFE. For a given equalization window size, the trellis memory, and hence the number of states and metric computations, for DFSE can be substantially less than that of an MLSE.
The prior art does not specifically discuss practical implementations of a DFSE. The obvious brute force method is to calculate the second sum in equation 3 whenever encountered. Such an implementation, however, can entail a great deal of complexity in terms of computations and memory.
It is therefore an object of the present invention to provide a DFSE that exhibits reduced computational complexity and/or memory requirements.
In accordance with one aspect of the present invention, the foregoing and other objects are achieved in a DFSE metric determination apparatus and method in which one or more tables of Decision Feedback Estimation (DFE) hypotheses are stored in a memory. DFE hypotheses are retrieved from the one or more tables of DFE hypotheses, and are used to determine the DFSE metric. The memory may, for example, be a single memory device or a plurality of memory devices.
In some embodiments, the DFE hypotheses may be precalculated for storage into the memory prior to performance of any steps of retrieving DFE hypotheses from the one or more tables of DFE hypotheses. In alternative embodiments, the one or more tables may start out empty. Then, DFSE metric determination includes determining whether a desired DFE hypothesis is not presently stored in the memory. If it is not, the DFE hypothesis is calculated, stored into the memory, and used to determine the DFSE metric. If that DFE hypothesis is later needed for another DFSE metric computation, it may then be retrieved from the table.
In accordance with another aspect of the invention, instead of a single table, a number, M, of tables of DFE hypotheses may stored in the memory, wherein M greater than 1, and wherein each of the M tables of DFE hypotheses stores a corresponding one of M groups of DFE hypotheses. In this case, the step of using retrieved values of the DFE hypotheses to determine the DFSE metric includes the step of using retrieved values of the DFE hypotheses from each of the M tables to determine the DFSE metric.
In still another aspect of the invention, MLSE hypotheses may also be stored into one or more tables, so that values may later be retrieved for use during the determination of a DFSE metric. In order to reduce memory requirements, the MLSE hypotheses may be stored into a number, MMLSE, of tables in a memory, wherein MMLSE greater than 1.